﻿using System;
using System.Collections.Generic;
using GeoAPI.Geometries;
using NetTopologySuite.Utilities;

namespace NetTopologySuite.Index.Strtree
{
	[Serializable]
	public abstract class AbstractSTRtree<T, TItem> where T : IIntersectable<T>, IExpandable<T>
	{
		protected AbstractSTRtree(int nodeCapacity)
		{
			Assert.IsTrue(nodeCapacity > 1, "Node capacity must be greater than 1");
			this._nodeCapacity = nodeCapacity;
		}

		public void Build()
		{
			if (this._built)
			{
				return;
			}
			object buildLock = this._buildLock;
			lock (buildLock)
			{
				if (!this._built)
				{
					this._building = true;
					this._root = ((this._itemBoundables.Count == 0) ? this.CreateNode(0) : this.CreateHigherLevels(this._itemBoundables, -1));
					this._itemBoundables = null;
					this._built = true;
					this._building = false;
				}
			}
		}

		protected abstract AbstractNode<T, TItem> CreateNode(int level);

		protected virtual IList<IBoundable<T, TItem>> CreateParentBoundables(IList<IBoundable<T, TItem>> childBoundables, int newLevel)
		{
			Assert.IsTrue(childBoundables.Count != 0);
			List<IBoundable<T, TItem>> list = new List<IBoundable<T, TItem>>();
			list.Add(this.CreateNode(newLevel));
			foreach (IBoundable<T, TItem> childBoundable in CollectionUtil.StableSort<IBoundable<T, TItem>>(childBoundables, this.GetComparer()))
			{
				if (this.LastNode(list).ChildBoundables.Count == this.NodeCapacity)
				{
					list.Add(this.CreateNode(newLevel));
				}
				this.LastNode(list).AddChildBoundable(childBoundable);
			}
			return list;
		}

		protected AbstractNode<T, TItem> LastNode(IList<IBoundable<T, TItem>> nodes)
		{
			return (AbstractNode<T, TItem>)nodes[nodes.Count - 1];
		}

		protected static int CompareDoubles(double a, double b)
		{
			return a.CompareTo(b);
		}

		private AbstractNode<T, TItem> CreateHigherLevels(IList<IBoundable<T, TItem>> boundablesOfALevel, int level)
		{
			Assert.IsTrue(boundablesOfALevel.Count != 0);
			IList<IBoundable<T, TItem>> list = this.CreateParentBoundables(boundablesOfALevel, level + 1);
			if (list.Count == 1)
			{
				return (AbstractNode<T, TItem>)list[0];
			}
			return this.CreateHigherLevels(list, level + 1);
		}

		public AbstractNode<T, TItem> Root
		{
			get
			{
				this.Build();
				return this._root;
			}
			set
			{
				this._root = value;
			}
		}

		public int NodeCapacity
		{
			get
			{
				return this._nodeCapacity;
			}
		}

		public bool IsEmpty
		{
			get
			{
				if (!this._built)
				{
					return this._itemBoundables.Count == 0;
				}
				return this.Root.IsEmpty;
			}
		}

		public int Count
		{
			get
			{
				if (this.IsEmpty)
				{
					return 0;
				}
				this.Build();
				return this.GetSize(this._root);
			}
		}

		protected int GetSize(AbstractNode<T, TItem> node)
		{
			int num = 0;
			foreach (IBoundable<T, TItem> boundable in node.ChildBoundables)
			{
				if (boundable is AbstractNode<T, TItem>)
				{
					num += this.GetSize((AbstractNode<T, TItem>)boundable);
				}
				else if (boundable is ItemBoundable<T, TItem>)
				{
					num++;
				}
			}
			return num;
		}

		public int Depth
		{
			get
			{
				if (this.IsEmpty)
				{
					return 0;
				}
				this.Build();
				if (this._itemBoundables.Count != 0)
				{
					return this.GetDepth(this._root);
				}
				return 0;
			}
		}

		protected int GetDepth(AbstractNode<T, TItem> node)
		{
			int num = 0;
			foreach (IBoundable<T, TItem> boundable in node.ChildBoundables)
			{
				if (boundable is AbstractNode<T, TItem>)
				{
					int depth = this.GetDepth((AbstractNode<T, TItem>)boundable);
					if (depth > num)
					{
						num = depth;
					}
				}
			}
			return num + 1;
		}

		protected void Insert(T bounds, TItem item)
		{
			Assert.IsTrue(!this._built && !this._building, "Cannot insert items into an STR packed R-tree after it has been built.");
			this._itemBoundables.Add(new ItemBoundable<T, TItem>(bounds, item));
		}

		protected IList<TItem> Query(T searchBounds)
		{
			this.Build();
			List<TItem> list = new List<TItem>();
			if (this.IsEmpty)
			{
				return list;
			}
			if (this.IntersectsOp.Intersects(this._root.Bounds, searchBounds))
			{
				this.Query(searchBounds, this._root, list);
			}
			return list;
		}

		protected void Query(T searchBounds, IItemVisitor<TItem> visitor)
		{
			this.Build();
			if (this.IsEmpty)
			{
				return;
			}
			if (this.IntersectsOp.Intersects(this._root.Bounds, searchBounds))
			{
				this.Query(searchBounds, this._root, visitor);
			}
		}

		private void Query(T searchBounds, AbstractNode<T, TItem> node, IList<TItem> matches)
		{
			foreach (IBoundable<T, TItem> boundable in node.ChildBoundables)
			{
				if (this.IntersectsOp.Intersects(boundable.Bounds, searchBounds))
				{
					if (boundable is AbstractNode<T, TItem>)
					{
						this.Query(searchBounds, (AbstractNode<T, TItem>)boundable, matches);
					}
					else if (boundable is ItemBoundable<T, TItem>)
					{
						matches.Add(((ItemBoundable<T, TItem>)boundable).Item);
					}
					else
					{
						Assert.ShouldNeverReachHere();
					}
				}
			}
		}

		private void Query(T searchBounds, AbstractNode<T, TItem> node, IItemVisitor<TItem> visitor)
		{
			foreach (IBoundable<T, TItem> boundable in node.ChildBoundables)
			{
				if (this.IntersectsOp.Intersects(boundable.Bounds, searchBounds))
				{
					if (boundable is AbstractNode<T, TItem>)
					{
						this.Query(searchBounds, (AbstractNode<T, TItem>)boundable, visitor);
					}
					else if (boundable is ItemBoundable<T, TItem>)
					{
						visitor.VisitItem(((ItemBoundable<T, TItem>)boundable).Item);
					}
					else
					{
						Assert.ShouldNeverReachHere();
					}
				}
			}
		}

		public IList<object> ItemsTree()
		{
			this.Build();
			IList<object> list = AbstractSTRtree<T, TItem>.ItemsTree(this._root);
			return list ?? new List<object>();
		}

		private static IList<object> ItemsTree(AbstractNode<T, TItem> node)
		{
			List<object> list = new List<object>();
			foreach (IBoundable<T, TItem> boundable in node.ChildBoundables)
			{
				if (boundable is AbstractNode<T, TItem>)
				{
					IList<object> list2 = AbstractSTRtree<T, TItem>.ItemsTree((AbstractNode<T, TItem>)boundable);
					if (list2 != null)
					{
						list.Add(list2);
					}
				}
				else if (boundable is ItemBoundable<T, TItem>)
				{
					list.Add(((ItemBoundable<T, TItem>)boundable).Item);
				}
				else
				{
					Assert.ShouldNeverReachHere();
				}
			}
			if (list.Count > 0)
			{
				return list;
			}
			return null;
		}

		protected abstract AbstractSTRtree<T, TItem>.IIntersectsOp IntersectsOp { get; }

		protected bool Remove(T searchBounds, TItem item)
		{
			this.Build();
			return this.IntersectsOp.Intersects(this._root.Bounds, searchBounds) && this.Remove(searchBounds, this._root, item);
		}

		private static bool RemoveItem(AbstractNode<T, TItem> node, TItem item)
		{
            IBoundable<T, TItem> boundable = null;
            foreach (IBoundable<T, TItem> boundable2 in node.ChildBoundables)
            {
                ItemBoundable<T, TItem> itemBoundable = boundable2 as ItemBoundable<T, TItem>;
                if (itemBoundable != null)
                //if (itemBoundable != null && itemBoundable.Item == item) // 暂时不知道怎么解决，运行到这会有问题 2018/9
                {
                    boundable = itemBoundable;
                }
            }
            if (boundable != null)
            {
                node.ChildBoundables.Remove(boundable);
                return true;
            }
            return false;
		}

		private bool Remove(T searchBounds, AbstractNode<T, TItem> node, TItem item)
		{
			bool flag = AbstractSTRtree<T, TItem>.RemoveItem(node, item);
			if (flag)
			{
				return true;
			}
			AbstractNode<T, TItem> abstractNode = null;
			foreach (IBoundable<T, TItem> boundable in node.ChildBoundables)
			{
				if (this.IntersectsOp.Intersects(boundable.Bounds, searchBounds) && boundable is AbstractNode<T, TItem>)
				{
					flag = this.Remove(searchBounds, (AbstractNode<T, TItem>)boundable, item);
					if (flag)
					{
						abstractNode = (AbstractNode<T, TItem>)boundable;
						break;
					}
				}
			}
			if (abstractNode != null && abstractNode.ChildBoundables.Count == 0)
			{
				node.ChildBoundables.Remove(abstractNode);
			}
			return flag;
		}

		protected IList<IBoundable<T, TItem>> BoundablesAtLevel(int level)
		{
			List<IBoundable<T, TItem>> list = new List<IBoundable<T, TItem>>();
			AbstractSTRtree<T, TItem>.BoundablesAtLevel(level, this._root, list);
			return list;
		}

		private static void BoundablesAtLevel(int level, AbstractNode<T, TItem> top, ICollection<IBoundable<T, TItem>> boundables)
		{
			Assert.IsTrue(level > -2);
			if (top.Level == level)
			{
				boundables.Add(top);
				return;
			}
			foreach (IBoundable<T, TItem> boundable in top.ChildBoundables)
			{
				if (boundable is AbstractNode<T, TItem>)
				{
					AbstractSTRtree<T, TItem>.BoundablesAtLevel(level, (AbstractNode<T, TItem>)boundable, boundables);
				}
				else
				{
					Assert.IsTrue(boundable is ItemBoundable<T, TItem>);
					if (level == -1)
					{
						boundables.Add(boundable);
					}
				}
			}
		}

		protected abstract IComparer<IBoundable<T, TItem>> GetComparer();

		private readonly object _buildLock = new object();

		private volatile AbstractNode<T, TItem> _root;

		private volatile bool _built;

		private volatile bool _building;

		private List<IBoundable<T, TItem>> _itemBoundables = new List<IBoundable<T, TItem>>();

		private readonly int _nodeCapacity;

		protected interface IIntersectsOp
		{
			bool Intersects(T aBounds, T bBounds);
		}
	}
}
